package com.gitee.feizns.explore.data_structure.graph;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * @author feizns
 * @since 2020/4/30
 */
public class GetKth {

    public static void main(String[] args) {
        System.out.println(getKth(12, 15, 2));
    }

    static TreeMap<Integer, TreeSet<Integer>> ranks = new TreeMap<>();

    public static int getKth(int lo, int hi, int k) {
        for (int i = lo; i <= hi; i++) {
            int v = weight(i);
            TreeSet<Integer> treeSet = ranks.getOrDefault(v, new TreeSet<>());
            treeSet.add(i);
            ranks.put(v, treeSet);
        }
        int q = 1;
        while ( !ranks.isEmpty() ) {
            TreeSet<Integer> value = ranks.pollFirstEntry().getValue();
            int size = value.size();
            if ( k < size + q ) {
                for (int i = 0; i < size; i++) {
                    Integer v = value.pollFirst();
                    if ( q == k )
                        return v;
                    q++;
                }
            }
            q += value.size();
        }
        return -1;
    }

    static Map<Integer, Integer> CACHE = new HashMap<>();

    private static int weight(int c) {
        if ( c == 1 )
            return 0;
        if ( CACHE.get(c) != null )
            return CACHE.get(c);
        if ( c % 2 == 0 ) {
            int v = weight(c / 2) + 1;
            CACHE.put(c , v);
            return v;
        } else {
            int v = weight(c * 3 + 1) + 1;
            CACHE.put(c, v);
            return v;
        }
    }

}
